package com.company;

import java.util.Arrays;

/**
 * @date : 2021/12/8 13:42
 * 堆排序问题
 */

public class P007_HeapSort {

    /**
     * @author lilei
     * @date 2020-09-09 16:00
     * @apiNote 堆排序
     * 堆排序是指利用堆积树这种数据结构所设计的一种排序算法，它是选择排序的一种。
     * 可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。
     * 完全二叉树：除了最后一层之外的其他每一层都被完全填充，并且所有节点都保持向左对齐。
     * 满二叉树：除了叶子节点之外的每一个节点都有两个孩子，每一层都被完全填充。
     * 完满二叉树：除了叶子节点之外的每一个节点都有两个孩子节点。
     * 堆排序是将数据看成完全二叉树、根据完全二叉树的特性来排序的一种算法
     * 最大堆要求节点的元素都不要小于其孩子，最小堆要求节点元素都不大于其孩子
     * 处于最大堆的根节点的元素一定是这个堆中的最大值
     * 完全二叉树特性：
     * 左边子节点位置 = 当前父节点的两倍 + 1
     * 右边子节点位置 = 当前父节点的两倍 + 2
     * 通过建堆、交换、建堆、交换……完成堆排序
     * 比较当前父节点是否大于子节点，如果大于就交换，直到一趟建堆完成
     */

    public static class HeapSort {

        public static void main(String[] args) {
            int count = 0;
            for (int i = 0; i < 1; i++) {
                // int[] arr = generateRandomArray(100, 100);
                int[] arr = {-26,1};
                int[] newArr = new int[arr.length];
                System.arraycopy(arr, 0, newArr, 0, arr.length);
                heapSort(arr);
                Arrays.sort(newArr);
                // System.out.println(Arrays.toString(arr));
                // System.out.println(Arrays.toString(newArr));

                if (!Arrays.equals(arr, newArr)) {
                    System.out.println("---start---");
                    System.out.println(Arrays.toString(arr));
                    System.out.println(Arrays.toString(newArr));
                    System.out.println("----end----");
                    count++;
                }

            }
            System.out.println(count);
        }

        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            }
            return arr;
        }

        public static void heapSort(int[] array) {
            // 完成一次建堆
            buildMaxHeap(array, array.length - 1);
            int size = array.length - 1;
            for (int i = 0; i < array.length; i++) {
                // 交换
                int temp = array[0];
                array[0] = array[(array.length - 1) - i];
                array[(array.length - 1) - i] = temp;

                // 调整位置
                buildHeap(array, 0, size);
                size--;
            }
        }

        /**
         * 建堆
         *
         * @param array           看作是完全二叉树
         * @param currentRootNode 当前父节点位置
         * @param size            节点总数
         */
        public static void buildHeap(int[] array, int currentRootNode, int size) {
            if (currentRootNode < size) {
                // 左子树和右子树的位置
                int left = 2 * currentRootNode + 1;
                int right = 2 * currentRootNode + 2;

                // 把当前父节点的位置看成是最大的
                int max = currentRootNode;

                if (left < size) {
                    // 如果比当前根元素要大，记录它的位置
                    if (array[max] < array[left]) {
                        max = left;
                    }
                }
                if (right < size) {
                    // 如果比当前根元素要大，记录它的位置
                    if (array[max] < array[right]) {
                        max = right;
                    }
                }
                // 如果最大的不是根元素位置，那么就交换
                if (max != currentRootNode) {
                    int temp = array[max];
                    array[max] = array[currentRootNode];
                    array[currentRootNode] = temp;

                    // 继续比较，直到完成一次建堆
                    buildHeap(array, max, size);
                }
            }
        }

        /**
         * 完成一次建堆，最大值在根的顶部（根节点）
         *
         * @param array 看作是完全二叉树
         * @param size  节点总数
         */
        public static void buildMaxHeap(int[] array, int size) {
            for (int i = size - 1; i >= 0; i--) {
                buildHeap(array, i, size);
            }
        }
    }
}
